package tree;

/**
 * 222. 完全二叉树的节点个数
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * <p>
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
 * 并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^h个节点。
 */
public class CountCompleteTreeNodes_222 {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftCnt = countNodes(root.left);
        int rightCnt = countNodes(root.right);
        return leftCnt + rightCnt + 1;
    }

    // 针对二叉树的解法：满二叉树的结点数为：2^depth - 1
    public int countNodes2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = 0;
        int rightDepth = 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }

        while (right != null) {
            right = right.right;
            rightDepth++;
        }

        // 如果是满二叉树，节点数量为2^depth - 1
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }

        // 不是满二叉树就继续遍历
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        CountCompleteTreeNodes_222 nodes222 = new CountCompleteTreeNodes_222();
        System.out.println(nodes222.countNodes(node1));

    }
}
